#include "List.cpp"

//给你一个链表数组，每个链表都已经按升序排列。
//
//请你将所有链表合并到一个升序链表中，返回合并后的链表。

 ListNode* MergeList( ListNode* l1, ListNode* l2){
    ListNode* p = l1;
    ListNode* q = l2;
    ListNode* pos = ( ListNode*) malloc(sizeof ( ListNode));
    pos->next = NULL;
    ListNode* head = pos;
    while (p!=NULL && q!= NULL) {
        if (p->data > q->data) {
            pos->next = q;
            pos = pos->next;
            q = q->next;
        }else {
            pos->next = p;
            pos = pos->next;
            p = p->next;
        }
    }

    if (p != NULL) {
        pos->next = p;
    }
    if (q != NULL) {
        pos->next = q;
    }
    return head->next;
}

 ListNode* mergeKLists( ListNode** lists, int listsSize){
    if (listsSize == 0) {
        return NULL;
    }
    ListNode* first = lists[0];
    for (int i = 1; i < listsSize; ++i) {
        first = MergeList(first,lists[i]);
    }
    return first;
}

